<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>数组转树 - 多种实现方法详解</title>
    <style>
        body {
            font-family: 'Arial', sans-serif;
            margin: 20px;
            background-color: #f5f5f5;
        }
        .container {
            max-width: 1200px;
            margin: 0 auto;
            background: white;
            padding: 20px;
            border-radius: 8px;
            box-shadow: 0 2px 10px rgba(0,0,0,0.1);
        }
        h1, h2 {
            color: #333;
            border-bottom: 2px solid #4CAF50;
            padding-bottom: 10px;
        }
        .method {
            margin: 30px 0;
            padding: 20px;
            border: 1px solid #ddd;
            border-radius: 5px;
            background-color: #fafafa;
        }
        .result {
            background-color: #f0f8ff;
            padding: 15px;
            border-left: 4px solid #2196F3;
            margin: 15px 0;
            white-space: pre-wrap;
            font-family: monospace;
        }
        .complexity {
            background-color: #fff3cd;
            padding: 10px;
            border-left: 4px solid #ffc107;
            margin: 10px 0;
        }
    </style>
</head>
<body>
    <div class="container">
        <h1>🌳 数组转树结构 - 详细实现与解析</h1>
        
        <div class="method">
            <h2>📊 测试数据</h2>
            <div id="testData"></div>
        </div>

        <div class="method">
            <h2>🚀 方法一：Map缓存法（推荐）</h2>
            <div class="complexity">
                <strong>时间复杂度：</strong>O(n) | <strong>空间复杂度：</strong>O(n)
            </div>
            <div id="method1Result"></div>
        </div>

        <div class="method">
            <h2>🔄 方法二：递归查找法</h2>
            <div class="complexity">
                <strong>时间复杂度：</strong>O(n²) | <strong>空间复杂度：</strong>O(n)
            </div>
            <div id="method2Result"></div>
        </div>

        <div class="method">
            <h2>⚡ 方法三：一次遍历法（最优）</h2>
            <div class="complexity">
                <strong>时间复杂度：</strong>O(n) | <strong>空间复杂度：</strong>O(n)
            </div>
            <div id="method3Result"></div>
        </div>

        <div class="method">
            <h2>🎯 方法四：支持多根节点</h2>
            <div class="complexity">
                <strong>时间复杂度：</strong>O(n) | <strong>空间复杂度：</strong>O(n)
            </div>
            <div id="method4Result"></div>
        </div>
    </div>

    <script>
        // 测试数据：扁平化的节点数组
        const testData = [
            { id: 1, name: "总部", parentId: null },
            { id: 2, name: "技术部", parentId: 1 },
            { id: 3, name: "市场部", parentId: 1 },
            { id: 4, name: "前端组", parentId: 2 },
            { id: 5, name: "后端组", parentId: 2 },
            { id: 6, name: "推广组", parentId: 3 },
            { id: 7, name: "销售组", parentId: 3 },
            { id: 8, name: "React小组", parentId: 4 },
            { id: 9, name: "Vue小组", parentId: 4 },
            { id: 10, name: "Java小组", parentId: 5 },
        ];

        // 显示测试数据
        document.getElementById('testData').innerHTML = `
            <div class="result">
原始扁平数组：
${JSON.stringify(testData, null, 2)}
            </div>
        `;

        // 方法一：Map缓存法（两次遍历）
        function arrayToTreeWithMap(arr) {
            console.log('🚀 执行方法一：Map缓存法');
            
            // 第一步：创建Map缓存，以id为key存储节点
            const nodeMap = new Map();
            const result = [];

            // 第一次遍历：初始化所有节点，添加children属性
            arr.forEach(item => {
                nodeMap.set(item.id, { 
                    ...item, 
                    children: [] 
                });
            });

            console.log('📝 Map缓存创建完成:', nodeMap);

            // 第二次遍历：建立父子关系
            arr.forEach(item => {
                const currentNode = nodeMap.get(item.id);
                
                if (item.parentId === null || item.parentId === undefined) {
                    // 根节点：没有父节点的节点
                    result.push(currentNode);
                } else {
                    // 子节点：找到父节点并加入其children数组
                    const parentNode = nodeMap.get(item.parentId);
                    if (parentNode) {
                        parentNode.children.push(currentNode);
                    }
                }
            });

            console.log('✅ 方法一执行完成');
            return result;
        }

        // 方法二：递归查找法
        function arrayToTreeRecursive(arr, parentId = null) {
            console.log('🔄 执行方法二：递归查找法，当前parentId:', parentId);
            
            return arr
                .filter(item => item.parentId === parentId)  // 找到当前层级的所有节点
                .map(item => ({
                    ...item,
                    children: arrayToTreeRecursive(arr, item.id)  // 递归查找子节点
                }));
        }

        // 方法三：一次遍历法（最优化）
        function arrayToTreeOnePass(arr) {
            console.log('⚡ 执行方法三：一次遍历法');
            
            const nodeMap = new Map();
            const roots = [];

            // 一次遍历完成所有操作
            arr.forEach(item => {
                // 如果节点已存在（可能之前作为某个节点的父节点被创建），则更新其属性
                if (nodeMap.has(item.id)) {
                    Object.assign(nodeMap.get(item.id), item);
                } else {
                    // 创建新节点
                    nodeMap.set(item.id, { ...item, children: [] });
                }

                const currentNode = nodeMap.get(item.id);

                if (item.parentId === null || item.parentId === undefined) {
                    // 根节点
                    roots.push(currentNode);
                } else {
                    // 确保父节点存在
                    if (!nodeMap.has(item.parentId)) {
                        nodeMap.set(item.parentId, { children: [] });
                    }
                    
                    const parentNode = nodeMap.get(item.parentId);
                    parentNode.children.push(currentNode);
                }
            });

            console.log('✅ 方法三执行完成');
            return roots;
        }

        // 方法四：支持多根节点和错误处理
        function arrayToTreeRobust(arr) {
            console.log('🎯 执行方法四：支持多根节点');
            
            if (!Array.isArray(arr) || arr.length === 0) {
                return [];
            }

            const nodeMap = new Map();
            const roots = [];
            const orphans = []; // 孤儿节点（找不到父节点的节点）

            // 第一步：创建所有节点
            arr.forEach(item => {
                if (item.id === undefined || item.id === null) {
                    console.warn('⚠️ 发现无效节点（缺少id）:', item);
                    return;
                }
                
                nodeMap.set(item.id, { 
                    ...item, 
                    children: [] 
                });
            });

            // 第二步：建立关系
            arr.forEach(item => {
                if (item.id === undefined || item.id === null) return;
                
                const currentNode = nodeMap.get(item.id);
                
                if (item.parentId === null || item.parentId === undefined) {
                    // 根节点
                    roots.push(currentNode);
                } else {
                    // 查找父节点
                    const parentNode = nodeMap.get(item.parentId);
                    if (parentNode) {
                        parentNode.children.push(currentNode);
                    } else {
                        // 找不到父节点，标记为孤儿节点
                        console.warn('⚠️ 发现孤儿节点（找不到父节点）:', item);
                        orphans.push(currentNode);
                    }
                }
            });

            console.log('✅ 方法四执行完成');
            console.log('📊 统计信息:', {
                总节点数: arr.length,
                根节点数: roots.length,
                孤儿节点数: orphans.length
            });

            return { 
                tree: roots, 
                orphans: orphans,
                stats: {
                    totalNodes: arr.length,
                    rootNodes: roots.length,
                    orphanNodes: orphans.length
                }
            };
        }

        // 执行测试并显示结果
        function runTests() {
            console.log('🔥 开始执行所有测试方法...\n');

            // 方法一测试
            console.group('方法一：Map缓存法');
            const result1 = arrayToTreeWithMap(testData);
            console.groupEnd();
            
            document.getElementById('method1Result').innerHTML = `
                <h3>💡 算法原理：</h3>
                <p>1. <strong>第一次遍历</strong>：创建Map缓存，为每个节点添加children数组</p>
                <p>2. <strong>第二次遍历</strong>：建立父子关系，将子节点添加到父节点的children中</p>
                <p>3. <strong>优势</strong>：利用Map的O(1)查找特性，避免嵌套循环</p>
                
                <h3>🌳 转换结果：</h3>
                <div class="result">${JSON.stringify(result1, null, 2)}</div>
            `;

            // 方法二测试
            console.group('方法二：递归查找法');
            const result2 = arrayToTreeRecursive(testData);
            console.groupEnd();
            
            document.getElementById('method2Result').innerHTML = `
                <h3>💡 算法原理：</h3>
                <p>1. <strong>递归思想</strong>：从根节点开始，递归查找每个节点的子节点</p>
                <p>2. <strong>过滤查找</strong>：每次递归都要遍历整个数组查找子节点</p>
                <p>3. <strong>缺点</strong>：时间复杂度较高O(n²)，但代码简洁易懂</p>
                
                <h3>🌳 转换结果：</h3>
                <div class="result">${JSON.stringify(result2, null, 2)}</div>
            `;

            // 方法三测试
            console.group('方法三：一次遍历法');
            const result3 = arrayToTreeOnePass(testData);
            console.groupEnd();
            
            document.getElementById('method3Result').innerHTML = `
                <h3>💡 算法原理：</h3>
                <p>1. <strong>动态创建</strong>：遍历过程中动态创建父节点（如果不存在）</p>
                <p>2. <strong>一次遍历</strong>：只需要一次遍历就能完成整个树的构建</p>
                <p>3. <strong>最优解</strong>：时间复杂度O(n)，空间复杂度O(n)，性能最佳</p>
                
                <h3>🌳 转换结果：</h3>
                <div class="result">${JSON.stringify(result3, null, 2)}</div>
            `;

            // 方法四测试
            console.group('方法四：支持多根节点');
            const result4 = arrayToTreeRobust(testData);
            console.groupEnd();
            
            document.getElementById('method4Result').innerHTML = `
                <h3>💡 算法原理：</h3>
                <p>1. <strong>错误处理</strong>：处理无效数据、缺少id的节点</p>
                <p>2. <strong>孤儿节点</strong>：识别并处理找不到父节点的节点</p>
                <p>3. <strong>统计信息</strong>：提供详细的转换统计信息</p>
                <p>4. <strong>生产就绪</strong>：适合在生产环境中使用的健壮实现</p>
                
                <h3>🌳 转换结果：</h3>
                <div class="result">树结构：
${JSON.stringify(result4.tree, null, 2)}

统计信息：
${JSON.stringify(result4.stats, null, 2)}</div>
            `;

            console.log('✅ 所有测试完成！');
        }

        // 页面加载完成后执行测试
        document.addEventListener('DOMContentLoaded', function() {
            runTests();
        });

        // 工具函数：深度优先遍历树结构
        function traverseTree(tree, callback) {
            function dfs(node, depth = 0) {
                callback(node, depth);
                if (node.children && node.children.length > 0) {
                    node.children.forEach(child => dfs(child, depth + 1));
                }
            }
            
            tree.forEach(root => dfs(root));
        }

        // 工具函数：计算树的深度
        function getTreeDepth(tree) {
            function getDepth(node) {
                if (!node.children || node.children.length === 0) {
                    return 1;
                }
                return 1 + Math.max(...node.children.map(getDepth));
            }
            
            return Math.max(...tree.map(getDepth));
        }

        // 导出到全局作用域，方便在控制台中测试
        window.arrayToTreeMethods = {
            mapCache: arrayToTreeWithMap,
            recursive: arrayToTreeRecursive,
            onePass: arrayToTreeOnePass,
            robust: arrayToTreeRobust,
            utils: {
                traverse: traverseTree,
                getDepth: getTreeDepth
            }
        };

        console.log('🎉 所有方法已导出到 window.arrayToTreeMethods');
        console.log('💡 你可以在控制台中使用这些方法进行测试');
    </script>
</body>
</html> 